function QuickSort() {}

QuickSort.quickSort = function(arr, startIndex, endIndex) {
    // 递归结束条件：startIndex大等于endIndex的时候
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素位置
    var pivotIndex = QuickSort._partition(arr, startIndex, endIndex);
    // 根据基准元素，分成两部分递归排序
    QuickSort.quickSort(arr, startIndex, pivotIndex - 1);
    QuickSort.quickSort(arr, pivotIndex + 1, endIndex);
}
    
QuickSort._partition = function(arr, startIndex, endIndex) {
    // 取第一个位置的元素作为基准元素（也可以选择随机位置）
    var pivot = arr[startIndex];
    var mark = startIndex;

    for(var i=startIndex+1; i<=endIndex; i++){
        if(arr[i]<pivot){
            mark ++;
            var p = arr[mark];
            arr[mark] = arr[i];
            arr[i] = p;
        }
    }

    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}


var arr = new Array(4,4,6,5,3,2,8,1);
QuickSort.quickSort(arr, 0, arr.length-1);
console.log(arr);